// 给定不同面额的硬币 coins 和一个总金额 amount。
// 编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
// 你可以认为每种硬币的数量是无限的。
// 输入：coins = `[1, 2, 5]`, amount = 11
// 输出：3
// 解释：11 = 5 + 5 + 1

// 思路，动态规划
// 1. `dp[i]`,凑成总金额i所需的最少个数
// 2. 递推公式，`dp[i] = Math.min(dp[i], dp[i-coins[j]] + 1)`
// 3. 初始化，`dp[0] = 0`,其他初始化为Infinity
// 4. 遍历顺序，内层和外层遍历谁都行，都为正序遍历
// 5. 举例

function coinChange(coins, amount) {
    let dp = new Array(amount + 1).fill(Infinity)
    dp[0] = 0
    for (let i = 0; i <= amount; i++) {
        for (let j = 0; j < coins.length; j++) {
            if (i >= coins[j]) {
                dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1)
            }
        }        
    }
    if (dp[amount] === Infinity) {
        return -1
    }
    return dp[amount]
}

let coins = [1, 2, 5], amount = 11
console.log(coinChange(coins, amount))

// 思路2，层序遍历
// 相当于是amount到0的最短路径问题
function coinChange2(coins, amount) {
    if (amount === 0) {
        return 0
    }
    let queue = [amount]
    let visited = new Set(queue)
    let step = 0
    while (queue.length) {
        let size = queue.length
        step++
        for (let i = 0; i < size; i++) {
            let cur = queue.shift()
            for (let j = 0; j < coins.length; j++) {
                if (coins[j] === cur) {
                    return step
                } else if (coins[j] < cur) {
                    if (!visited.has(cur - coins[j])) {
                        queue.push(cur - coins[j])
                        visited.add(cur - coins[j])
                    }
                }        
            }
        }
    }
    return -1
}

console.log(coinChange2(coins, amount))